|
The Ehrenfeucht–Mycielski sequence is a recursively defined sequence of binary digits with pseudorandom properties, defined by . ==Definition== The sequence starts with the single bit 0; each successive digit is formed by finding the longest suffix of the sequence that also occurs earlier within the sequence, and complementing the bit following the most recent earlier occurrence of that suffix. (The empty string is a suffix and prefix of every string.) For example, the first few steps of this construction process are: #0: initial bit #01: the suffix "" of "0" occurs earlier, most-recently followed by a 0, so add 1 #010: the suffix "" of "01" occurs earlier, most-recently followed by a 1, so add 0 #0100: the suffix "0" of "010" occurs earlier, most-recently followed by a 1, so add 0 #01001: the suffix "0" of "0100" occurs earlier, most-recently followed by a 0, so add 1 #010011: the suffix "01" of "01001" occurs earlier, most-recently followed by a 0, so add 1 #0100110: the suffix "1" of "010011" occurs earlier, most-recently followed by a 1, so add 0 The first few digits of the sequence are: :010011010111000100001111... . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ehrenfeucht–Mycielski sequence」の詳細全文を読む スポンサード リンク
|